import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = new int[]{1,2,4,};
        System.out.println(s.shortestSubarray(nums, 4));
    }

    public int shortestSubarray(int[] nums, int k) {
        /**
         * 和至少为k的最短子数组的长度*/
        // 1 预处理
        int n = nums.length;

        // 2 求前缀和（使用虚拟位置节点，存储什么都不选的情况，这样可以表示全选元素的情况）
        long[] previousSum = new long[n+1];
        for(int i = 1; i <= n; i++) {
            // -上一个前缀和 + 当前值 = 当前前缀和
            previousSum[i] = previousSum[i-1] + nums[i-1];
        }

        // 3 使用单调队列维护可能匹配项
        // -求最小值，故我初始化为最大值
        int minWidth = 0x3f3f3f3f;
        // -存储组合（前缀和：下标）
        Deque<long[]> queue = new LinkedList<>();
        queue.addLast(new long[]{0, 0});
        for(int i = 1; i <= n; i++) {
            // -维护队头，满足条件（记录=》出队头=》循环）
            while(!queue.isEmpty() && previousSum[i] - queue.peekFirst()[0] >= k) {
                minWidth = Math.min(minWidth, (int)(i - queue.pollFirst()[1]));
            }
            // -走到此处，队头维护完毕，维护队尾
            while(!queue.isEmpty() && previousSum[i] <= queue.peekLast()[0]) {
                queue.pollLast();
            }
            queue.offerLast(new long[]{previousSum[i], i});
        }

        // 4 返回值
        return minWidth == 0x3f3f3f3f ? -1 : minWidth;
    }
}
